In general, rendering is a process by which an object may be drawn on a display, printer or other such device. Computer generated imagery, in particular, is a field in which realistic images of an object such as a complex scene are presented on a computer display using a rendering algorithm. An object being rendered typically is created by a designer using a modeling program to create a complex geometric database and then a rendering algorithm is executed to process that database and create the image on the display.
Frequently, complex objects such as a scene of an office having numerous polygons, contain step edges and other high frequency detail which has posed serious aliasing problems for rendering algorithms. These aliasing problems result in computer generated images on a display which have jaggies and other familiar aliasing artifacts. In general, the potential for aliasing arises in computer graphics because the mathematical representations used to describe images, e.g. polygons, contain energy at arbitrarily high spatial frequencies, while the sampled rasters used to display or print images are limited to a finite range of spatial frequencies.
More specifically, let I(x,y) be a vector-valued function that gives the color of each point on an idealized, continuous display screen for the idealized mathematical representation of a computer graphics image. If a raster image is computed by directly sampling I(x,y) at the center of each output pixel, then any spatial frequency content in I(x,y) above half the sampling rate will alias to a lower frequency and cause disturbing visual artifacts. In non-mathematical terms, in complex scenes, numerous primitives may be visible within an individual pixel, and when this occurs, if a pixel is colored according to the color of the primitive which happens to be visible at pixel center, this color is likely to differ greatly from the local average, causing a disturbing visual artifact.
There are three approaches for dealing with the aliasing problem. The first approach is to adjust the number, locations or weights of the samples to attenuate the visible aliased imagery. The second approach is to try to detect aliasing artifacts in the rendered image and remove them by post-processing. The third approach, and the only one capable of guaranteed accuracy, is to compute or approximate the convolution I(x,y) * f(x,y) of the image I(x,y) with a low-pass filter f(x,y) at each output pixel using analytic or other means. Each of these approaches has its own problems.
The first approach i.e., adjusting the number and location of the samples and the filter kernels used to combine them, can substantially reduce the severity of aliasing artifacts. However, this approach provides no guarantees about the quality of the result and can produce unacceptable errors in cases where a large number of primitives are visible within a single pixel. The basic problem is that it is not known in advance what sampling rate will be required for any particular region of the image, and an algorithm that uses a fixed sampling rate would be unable to deal with extremely complex scenes where large numbers of polygons are frequently visible in a single pixel.
The second approach i.e., post-processing, has limited potential because it begins after the sampling process. If geometric primitives are large compared to pixels, then a post process can sometimes effectively infer edges from the sampled image and soften them to attenuate aliasing artifacts. However, if large numbers of primitives are visible within individual pixels, too much information is lost in the sampling process to allow a post process to compute an acceptable reconstruction.
The third approach i.e., convolution before sampling, is the only technique which, in principle, is capable of eliminating aliasing entirely. From a theoretical perspective, if the function I(x,y) is convolved with the appropriate sinc function, it will be low-pass filtered below the Nyquist sampling rate before sampling and no aliasing will occur. From a practical perspective, however, the ideal sinc function generates ringing (Gibbs phenomenon) at step edges, and therefore other filters such as triangular filters, Gaussians, raised cosine filters, Hamming windows, etc. might be used. Nevertheless, whatever filter is chosen, rendering with this approach requires (a) identifying visible geometric primitives affecting each output pixel and (b) filtering them.
Most visible surface algorithms capable of finding all the geometric primitives potentially affecting a single pixel require examining each primitive in the model of the scene. For ordinary purposes with moderately complex models, this is not a serious limitation. For an extremely complex model, such as one having 100 million primitives, however, this poses a major problem. Examining and processing each of the 100 million primitives will take a prohibitively long time on current computers. The only practical way of rendering the model is to use an algorithm which does work roughly proportional to the visible complexity of the scene rather than the size of the entire model. In general, such algorithms are known as "output sensitive".
Prior application Ser. No. 08/100,113, filed Jul. 30, 1993, entitled "Rendering of 3D Scenes on a Display Using Hierarchical Z-Buffer Visibility", by Greene et al., is assigned to the assignee of the present invention, and is incorporated by reference herein in its entirety. This prior application does work roughly proportional to the visible complexity of the scene by employing a Z-Buffer or depth buffer rendering algorithm for visible surface display of a complex 3D scene. In general, a Z-Buffer rendering algorithm uses a frame buffer F which stores color values of a scene for display, and a Z-Buffer, with the same number of entries as the frame buffer, in which a Z or depth value is stored for each pixel. Typically, in rendering a frame F, the Z-Buffer is initialized to the Z-value of the far clipping plane, and the frame buffer is initialized to the background color. Z values stored in the Z-Buffer range between a value representing the front clipping plane and a value representing the far clipping plane. Polygons are scan converted into the frame buffer and during the scan conversion process, if the polygon point being scan converted at (x, y) is nearer to the viewer than is the point whose color and depth are currently stored in the buffers, then the new point's color and depth replace the old values.
In this prior patent application, an algorithm to accelerate the Z-Buffer rendering of complex environments is disclosed. This algorithm employs two data structures which are an object-space octree and an image-space depth pyramid. The algorithm accelerates the rendering process by culling hidden geometry very effectively for scenes with high depth complexity. With this Z-Buffer rendering, geometry which is hidden on all point samples can be culled whether or not portions of the geometry are visible in between these samples. However, this type of culling can result in aliasing artifacts resulting from failing to consider portions of the geometry which may be visible in between the samples.